"Fantasy" là một bài hát nhạc pop, R&B đương đại và dance-pop tiết tấu nhanh, hòa trộn các yếu tố của funk, hip hop và bubblegum pop.[2][3][4] Bản phối lại, với sự xuất hiện của O.D.B trong đoạn rap, cũng sáp nhập thể loại hip-hop trong đoạn dẫn của bài hát. "Fantasy" phần lớn sử dụng nhịp bass và bộ gõ, cũng như đoạn nhạc mẫu từ "Genius of Love".[2] Bài hát có phân số chỉ nhịp trứ danh, với nhịp độ 127 nhịp một phút vừa phải. Quãng giọng của Carey trong bài hát trải dài từ D3 đến F6.[4] Bài hát chứa đoạn lời hợp xướng do Carey sáng tác, đồng thời phát triển giai điệu bài hát cùng nhịp điệu gốc. Phần nhạc khí và sản xuất được Dave Hall trình bày, trong khi chính ông cũng tham gia đồng cải biên và sản xuất bài hát.[2] Thành viên của nhóm Tom Tom Club, Tina Weymouth, Chris Frantz, Steven Stanley và Adrian Belew đều được ghi danh làm tác giả của bài hát do phần nhạc mẫu mà họ sáng tác.[2]